/**
 * 求： arr中每一项前面和后面第一个比它小的值得位置
 */

const Arr = [1, 3, -1, -3, 5, 3, 6, 7, 8, 10, 9];

function main(arr){
  // 单调递增队列
  let q = []; 
  // arr[i] 前面第一个比它小的值得下标
  let pre = [];
  // arr[i] 后面第一个比它小的值得下标
  let next = [];

  for( let i = 0; i < arr.length; i++){
    while( q.length && arr[i] < arr[q[q.length - 1]] ){
      // i 是被踢出元素后面第一个比它值大的下标
      let index = q.pop(); // pop维护单调性
      next[index] = i;
    }

    if(q.length == 0) {
      // 前面没有比当前值小的值
      pre[i] = -1;
    } else {
      // q最后一个值就是当前值前面第一个比它小的值
      pre[i] = q[q.length - 1]
    }

    // 维护队列单调性
    q.push(i)
  }

  // 队列中剩余的元素后面没有比它小的值
  while (q.length) {
    next[q[q.length - 1]] = arr.length;
    q.pop();
  }
  console.log(pre, next);
}
main(Arr);